Intrusion detection systems employ pattern matching techniques on network data in order to identify strings of data that are found in exploits that are known to have been used to inflict damage on target networks and systems. Specifically, pattern matching is used by intrusion detection systems to match network data to a set of signatures that represent all currently known attacks at a given time. Since the amount of network data that requires scanning and the set of signatures that represent attacks are both typically large, it is usually impossible to scan network data for all signatures in real time. In addition, applying all signatures in the current set, many of which may require numerous compare operations only to find in the end the data stream does not match the signature, results in a number of unnecessary operations. Further inefficiency results where recursion is present within one or more of the signatures, as the same signature (or component thereof) may need to be applied multiple times. Consequently, most intrusion detection systems categorize the set of signatures to be matched into subsets having common criteria so that the number of signatures that are applied to a given input data stream is minimized.
One approach used to filter out signatures that do not apply to the current input data stream is prefix based filtering. With this technique, the first few bytes of all signatures are identified, and the signatures that have a common prefix are grouped together. Only those signatures included in a subset with a common prefix that matches the corresponding initial bytes of the target data stream are applied to the target data stream, thus saving resources on unnecessarily processing other signatures that do not have the given prefix. However, while prefix based filtering narrows the number of signatures to be applied somewhat, it fails at preventing unnecessary compare operations and/or iterations of signature matching for signatures that are applied to a given data stream. In addition, prefix based filtering does not prevent the inefficiency that can result from attempting to apply a signature before all the data required to fully apply the signature has been received.
Thus, there is a need to enhance the performance of signature based pattern matching by significantly reducing unnecessary iterations of full signature matching.